package com.leetcode.algorithm.y22.m06;

/**
 * 55. 跳跃游戏
 * 
 * https://leetcode.cn/problems/jump-game/
 * 
 * @author jie.deng
 *
 */
class Question0055Solution01 {

	public boolean canJump(int[] nums) {
		int len = nums.length;
		// DP状态定义：dp[i]表示是否能够到达第i个下标
		boolean[] dp = new boolean[len];
		
		// 状态初始化
		dp[0] = true;
		
		for (int i = 1; i < len; i++) {
			// 第i个下标由之前的第i-1、i-2、...0个下标跳跃而来，有一个可达即可达
			for (int j = i - 1; j >= 0; j--) {
				if (dp[j] && nums[j] > 0 && j + nums[j] >= i) {
					dp[i] = true;
					break;
				}
			}
		}
		return dp[len - 1];
	}

}